// 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，
// 并返回其长度。如果不存在符合条件的连续子数组，返回 0。

// 示例: 

// 输入: s = 7, nums = [2,3,1,2,4,3]
// 输出: 2
// 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
// 进阶:

// 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

#include <vector>

using namespace std;

// 暴力搜索
// O(N^2)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        int res{INT_MAX};
        for (int i{0}; i < n; ++i) {
            int sum{0};
            for (int j{i}; j < n; ++j) {
                sum += nums[j];
                if (sum >= s) { // 有可能所有的数字加起来也没有s大，这样的话res就可能是INT_MAX
                    res = min(j - i + 1, res);
                    break;
                }
            }
        }
        res = (res == INT_MAX ? 0 : res);
        return res;
    }
};

// 前缀和+二分查找
// O(NlogN)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        int res{INT_MAX};
        vector<int> sums(n + 1, 0); // 前缀和
        for (int i{1}; i <= n; ++i) {
            sums[i] = sums[i-1] + nums[i-1];
        }
        for (int i{1}; i <= n; ++i) {
            int target = s + sums[i-1];
            auto bound = lower_bound(sums.begin(), sums.end(), target);
            if (bound != sums.end()) res = min(res, static_cast<int>((bound - sums.begin()) - (i - 1)));
        }
        return res == INT_MAX ? 0 : res;
    }
};

// 双指针，滑动窗口
// O(N)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        int res{INT_MAX};
        int beg{0};
        int end{0};
        int sum{0};
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                res = min(res, end - beg + 1);
                sum -= nums[beg];
                ++beg;
            }
            ++end;
        }
        return res == INT_MAX ? 0 : res;
    }
};